package algorithm.t202111;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/4 8:52
 * @description :3道
 */
public class t20211104 {


    //367.有效的完全平方数
    public boolean isPerfectSquare(int num) {
        int count = 1;

        while (num > 0) {
            num -= count;
            count += 2;
        }

        return num == 0;
    }

    //213.打家劫舍||
    public int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }

        //明确要抢第一间
        int[] dp1 = new int[nums.length + 1];
        dp1[0] = 0;
        dp1[1] = nums[0];
        for (int i = 2; i < dp1.length; i++) {
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i - 1]);
        }
        int max_one = dp1[nums.length - 1];

        //明确不抢第一间
        int[] dp2 = new int[nums.length + 1];
        dp2[0] = 0;
        dp2[1] = 0;
        for (int i = 2; i < dp2.length; i++) {
            dp2[i] = Math.max(nums[i - 1] + dp2[i - 2], dp2[i - 1]);
        }
        int max_tow = dp2[nums.length];

        return Math.max(max_one, max_tow);

    }

    //55.跳跃游戏
    public boolean canJump(int[] nums) {
        if (nums == null) {
            return false;
        }
        int k = 0;
        for (int i = 0; i <= k; i++) {
            //第i个元素可以跳到的最远距离
            int temp = nums[i] + i;

            k = Math.max(k, temp);//更新更远的距离

            //如果最远距离已经大于或等于最后一个元素的下标,则说明能跳过去
            if (temp >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        t20211104 t20211104 = new t20211104();
        System.out.println(t20211104.canJump(new int[]{1}));

    }

}
